给表达式添加运算符(回溯算法解决)
The following article is from 数据结构和算法 Author 博哥
问题描述
来源:LeetCode第282题
难度:困难
给定一个仅包含数字0-9的字符串num和一个目标值整数target,在num的数字之间添加二元运算符(不是一元)+、-或*,返回所有能够得到目标值的表达式。
示例 1:
输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"]
示例 2:
输入: num = "232", target = 8
输出: ["2*3+2", "2+3*2"]
示例 3:
输入: num = "105", target = 5
输出: ["1*0+5","10-5"]
示例 4:
输入: num = "00", target = 0
输出: ["0+0", "0-0", "0*0"]
示例 5:
输入: num = "3456237490", target = 9191
输出: []
提示:
1<=num.length<=10
num仅含数字
-2^31<=target<=2^31-1
回溯算法解决
这题是让在数字之间添加“+”,“-”,“*”三种符号,变成一个算术表达式,并且让算术表达式的结果等于target。解题思路就是使用回溯算法列举所有可构成的算术表达式,然后计算他们的值。
这题我们可以把它看做是一颗n叉树,除了第一个数字以外,其他的每个数字都可以在他的前面添加“+”,“-”,“*”这三种符号,这里以示例一为例画个图来看一下。
来看个视频
我们可以看到这题和566,DFS解目标和问题有点相似,不同的是第566题只能添加“+”和“-”,而这题还可以添加“*”,这里要注意“*”的优先级要比“+”和“-”高。所以在回溯算法中我们需要使用一个变量preNum来记录前面连续相乘的积,还有一点就是这里的数字需要我们截取,截取的时候数字必须是有效的,也就是数字的最前面不能是0,比如“05”这种就是无效数字。来看下代码
public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<>();
dfs(res, num, target, 0, 0, 0, "");
return res;
}
/**
* @param res 返回的结果
* @param num 字符串num
* @param target 目标值target
* @param index 访问到字符串的第几个字符
* @param preNum 前面的连续乘积(乘法的时候会用到)
* @param sum 表达式前面计算得到的和
* @param path 算术表达式,可以看做n叉树的路径
*/
private void dfs(List<String> res, String num, int target, int index, long preNum, long sum, String path) {
//字符串num中所有元素都遍历完了,要指针遍历
if (index >= num.length()) {
//如果表达式的值等于target,说明找到了一个合适的表达式,
//就把他加入到集合res中
if (sum == target) {
res.add(path);
}
return;
}
for (int i = index; i < num.length(); i++) {
//类似于05,07这样以0开头的数字要过滤掉
if (i != index && num.charAt(index) == '0')
break;
//截取字符串,转化为数字
long number = Long.parseLong(num.substring(index, i + 1));
if (index == 0) {
//因为第一个数字前面是没有符号的,所以要单独处理
dfs(res, num, target, i + 1, number, number, "" + number);
} else {
//在当前数字number前面可以添加"+","-","*"三种符号。
//数字number前添加"+"
dfs(res, num, target, i + 1, number, sum + number, path + "+" + number);
//数字number前添加"-"
dfs(res, num, target, i + 1, -number, sum - number, path + "-" + number);
//数字number前添加"*"
dfs(res, num, target, i + 1, preNum * number,
sum + preNum * number - preNum, path + "*" + number);
}
}
}
程序员专属卫衣
商品直购链接 👇 推荐阅读:
每日打卡赢积分兑换书籍入口